Graphic workstations are devices that display computer-generated images on a display, typically a raster scan cathode ray tube (CRT). Images may originate from various sources, such as a mathematical model or a document scanner. Regardless of their origin, however, images are ultimately represented as an array of data values. Each data value specifies the intensity of a corresponding elemental physical area of the face of the CRT, called a pixel. If the CRT is a color CRT, each data value specifies the color of a pixel.
To cause the image to appear on the CRT, the pixel data values are first written into a dedicated high-speed bitmap memory associated with the workstation. The bitmap memory (also called a frame buffer) is arranged as a two-dimensional array, with each bitmap memory location corresponding to a physical pixel location. The pixel values are repetitively and sequentially read from the bitmap memory, in synchronism with the CRT's horizontal and vertical refresh timing. In color workstations, three digital-to-analog converters (DACs) are then used to generate three analog signals from the sequence of pixel values, with one analog signal for each of the red, green, and blue color intensity inputs of the CRT.
Creating an image as a sequence of pixel values can be quite calculation-intensive. Most workstations thus usually include a graphics subsystem which operates on high-level graphic object descriptions, or primitives, to produce the series of pixel values, as well as corresponding bitmap addresses into which the pixel values should be written. Common graphics operations such as translation and scaling, as well as more complicated functions such as three-dimensional to two-dimensional conversion, anti-aliasing, and shading are thus performed by the graphics subsystem. This frees the applications programmer from the drudgery of specifying the value and location of each pixel.
For example, an application program running on a host processor associated with the workstation may generate a graphic primitive that instructs the subsystem to draw a shaded trapezoid. The primitive includes a list of the locations of the trapezoid's vertices, a particular starting color, and x-coordinate and y-coordinate color increments. The subsystem then executes this primitive to cause the correct pixel values to be written into the correct locations of bitmap memory, using the start color and color increments.
The subsystem calculates each pixel value as a fixed-point number having an integer part and a fractional part. The integer part is typically limited to the number of bits in the bitmap memory word size. The pixel values are first computed with high resolution, and then rounded up or down to the nearest integer value, before being written into bitmap memory. This rounding technique provides transitions between colors in the correct places in the image.
The quality of the resulting image depends quite noticeably upon the number of bits used to specify each pixel value. In other words, the greater the number of bits in each word of the bitmap memory, the larger the range of available colors and intensities. It is generally agreed that a word size of twenty-four bits, with eight bits allocated to each of the three color channels, is needed to approach the image quality of a standard color television.
Despite the ever-decreasing price of semiconductors, however, bitmap memory is still relatively expensive, so that a workstation having a twenty-four bit bitmap memory can be quite costly. In addition, most applications do not require the use of all 2.sup.24 possible colors simultaneously, and a much smaller subset, say 16 colors, is sufficient. Accordingly, the applications programmer can specify which 16 colors are needed. The 16 twenty-four bit color values are not directly fed to the DACs, but rather, are stored in another memory, called a color look-up table (LUT). Each pixel value is then used as an address input to the LUT. The data output from the LUT is then used to control the DACs. This allows each pixel data word in the bitmap memory to be only four bits wide (2.sup.4= 16), and yet the 16 colors can be selected from the entire range of 2.sup.24 possible colors.
However, there is a disadvantage to the foregoing arrangement, as only sixteen of the 2.sup.24 colors can be displayed simultaneously. This compromise can be accepted in many applications, such as in presentation of two-dimensional images. However, the realism of a three-dimensional image depends heavily upon how well it is shaded. Sixteen shades of a given color do not afford the necessary gradual change from dark to light to provide a sufficiently realistic image of a round object as it is viewed in normal sunlight. This is because there will be a visible line where the intensity levels change, resulting in readily observable steps in the shaded image. It is generally believed that a four-bit wide bitmap memory results in poor shading of three-dimensional objects, since realism is achieved by gradual change over many shades and not by discrete steps between a few shades.
It is known that when displaying shaded images on a graphic display, the different color intensities can be blended, or "dithered," to prevent the human eye from observing intensity changes as discrete steps. Thus, random transitions can be generated in the pixel data word's least significant bits by adding random numbers to the output of the LUTs. This approach can create the illusion of having a greater range of colors, especially when a display such as a CRT is viewed at a distance of many feet. However, in other applications, such as computer workstations, where the CRT is most often viewed at a distance of one to three feet, the human eye may perceive a "flickering" effect as the pixel values change at the CRT scan rate.
Another technique called "ordered dithering" can be used to blend the intensity steps. This technique adds a predetermined random number to the fixed-point calculated pixel values before they are rounded to the nearest integer. The predetermined random number is determined by using the bitmap address bits of each pixel value as an index into a fixed array of predetermined fractional numbers. The fractional number addressed thereby is then added to or subtracted from the corresponding pixel value. The result is rounded and stored in the bitmap memory.
This process results in a dithering effect, because some pixel values will be changed enough to cross the intensity threshold into the next highest intensity. While the ordered dither technique provides visual blending along the boundary between intensity regions, a careful human eye can discern the resulting predetermined patterns on the CRT.
What is needed is a way to improve image quality by smoothing the discrete edges which are often visible along the boundary between intensity regions, especially in shaded images. The technique should improve image quality without increasing the number of colors required to be simultaneously displayed. In addition, it should be cost-effective, and avoid the need to increase the word size of the bitmap memory or the color look-up table. For the effect to be natural, the probability of dithering a particular pixel should increase as its distance to an intensity boundary decreases.